package a

import (
	"bufio"
	"container/heap"
	"fmt"
	"github.com/gin-gonic/gin"
	"gomvc/app/utils"
	"image"
	"math"
	"os"
	"strconv"
	"strings"
	"sync"
	"time"
)

type ht struct {
	landJx map[string]struct{}
	landCl map[string]struct{}
}

var Ht = ht{}

type HtAStarReq struct {
	Start []float64 `json:"start"`
	End   []float64 `json:"end"`
}

type Config struct {
	Motions [][2]float64
}

var landMap = AllWhiteIntTest(120.0879, 36.2606, 0.0001, 10000)

//var landMapBig = AllWhiteIntTest(120.0879, 36.2606, 0.001, 1000)

var landMapBig = readLandTxt("./public/image/0.001.txt")

var allNum = 0

// 由于有分段的设计，找一段的方法抽出来
func findOnePath(req HtAStarReq, angleNum int, step float64, isOut bool) []string {
	costMap := map[[2]int]float64{
		[2]int{
			int(math.Round(req.Start[0] * 10000)),
			int(math.Round(req.Start[1] * 10000)),
		}: 0,
	}
	relationMap := map[[2]int][3]int{
		[2]int{
			int(math.Round(req.Start[0] * 10000)),
			int(math.Round(req.Start[1] * 10000)),
		}: [3]int{
			int(math.Round(req.Start[0] * 10000)),
			int(math.Round(req.Start[1] * 10000)),
			0,
		},
	}

	grayMap := make(map[[2]int]int, 200000)
	openList := &MinHeap{}
	heap.Init(openList)
	heap.Push(openList, [3]float64{0, req.Start[0], req.Start[1]})

	//motions := GetMotions(angleNum)
	//8方向
	motions := [][2]float64{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}}
	//num := 0
	//var items [][3]float64
	for {
		//num++
		allNum++
		//取出open中的最小值，每次计算一个当前点与终点的方向当作动态方向
		minItem := heap.Pop(openList).([3]float64)
		//对minItem进行正方形涂灰
		//paintGray(minItem, grayMap, step, 0.001)

		//每隔5000个报数一次
		//距离终点的距离足够近，退出循环
		if math.Abs(minItem[1]-req.End[0]) < 0.005 && math.Abs(minItem[2]-req.End[1]) < 0.005 {
			path := getPath(relationMap, [2]int{int(math.Round(req.Start[0] * 10000)), int(math.Round(req.Start[1] * 10000))}, [2]int{int(math.Round(minItem[1] * 10000)), int(math.Round(minItem[2] * 10000))}, [2]int{int(math.Round(req.End[0] * 10000)), int(math.Round(req.End[1] * 10000))})
			fmt.Println("heap推出的可能的点数:", allNum)
			return path
		}

		//numLand := 0
		//	遍历32个方向

		for idx, sN := range getNeighbor(minItem, motions, grayMap, step, isOut) {
			//fmt.Println(sN)

			if sN[0] > 800.0 {
				continue
			}

			latInt := int(math.Round(sN[0] * 10000))
			lonInt := int(math.Round(sN[1] * 10000))

			minLatInt := int(math.Round(minItem[1] * 10000))
			minLonInt := int(math.Round(minItem[2] * 10000))

			offset := 0.00014
			if idx < 4 {
				offset = 0.0001
			}

			newCost := costMap[[2]int{
				minLatInt, minLonInt,
			}] + offset

			_, ok := costMap[[2]int{
				latInt, lonInt,
			}]

			if !ok {
				costMap[[2]int{
					latInt, lonInt,
				}] = 999.0
			}
			t31 := time.Now().UnixNano()

			if newCost < costMap[[2]int{
				latInt, lonInt,
			}] {
				costMap[[2]int{
					latInt, lonInt,
				}] = newCost
				relationMap[[2]int{
					latInt, lonInt,
				}] = [3]int{minLatInt, minLonInt, idx}
				//heap.Push(openList, [3]float64{newCost + getDistanceWeight(req.End[0], req.End[1], sN[0], sN[1], minItem), sN[0], sN[1]})
				heap.Push(openList, [3]float64{newCost + getDistance(req.End[0], req.End[1], sN[0], sN[1]), sN[0], sN[1]})

			}
			t32 := time.Now().UnixNano()
			allT3 += int(t32 - t31)
		}

	}
}

// HtAStar 开始
func (ctl *ht) HtAStar(c *gin.Context) {
	allNum = 0
	t1 := time.Now().UnixNano()
	var req HtAStarReq
	_ = c.ShouldBind(&req)
	//打印起始点和目标点
	fmt.Println("起始点---->", req.Start, "目标点---->", req.End)
	//cellSize := 0.0001
	step := 0.005
	angleNum := 32

	allT1 = 0
	allT2 = 0
	allT3 = 0

	var pathMid []string

	pathMid = findOnePath(req, angleNum, step, true)

	t2 := time.Now().UnixNano()
	c.JSON(200, gin.H{
		"code": 0,
		"msg":  "成功",
		"data": gin.H{
			"lines": pathMid,
			"t":     (t2 - t1) / 1e6,
			"num":   allNum,
			"gdNum": len(pathMid),
		},
	})
}

// GetMotions 获取n方向
func GetMotions(angle int) [][2]float64 {
	var motions [][2]float64
	motions = append(motions, [2]float64{})
	for i := 0; i < angle; i++ {
		motions = append(motions, [2]float64{math.Cos(float64(i) * 2 * math.Pi / float64(angle)), math.Sin(float64(i) * 2 * math.Pi / float64(angle))})
	}
	return motions
}

// MinHeap 小顶堆
type MinHeap [][3]float64

func (h MinHeap) Len() int      { return len(h) }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h MinHeap) Less(i, j int) bool {
	return h[i][0] < h[j][0]
} // 小顶堆
func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.([3]float64))
}
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func (h *MinHeap) downHeap(index int) {
	n := len(*h)
	for {
		childIndex := 2*index + 1
		if childIndex >= n {
			break
		}

		if childIndex+1 < n && (*h)[childIndex+1][0] < (*h)[childIndex][0] {
			childIndex++
		}

		if (*h)[index][0] <= (*h)[childIndex][0] {
			break
		}

		// 交换当前节点和子节点
		(*h).Swap(index, childIndex)
		index = childIndex
	}
}

func includesNumber(number, target, tolerance int) bool {
	//diff := math.Abs(number - target)
	//return diff <= tolerance

	return math.Abs(float64(number)-float64(target)) <= float64(tolerance)
}

func AllWhiteIntTest(minLng, maxLat, step float64, precision float64) map[[2]int]struct{} {
	//120.38669616044902 120.08785992 36.260629574755185 35.96465704
	landM := make(map[[2]int]struct{})
	f1, _ := os.Open("./public/image/qd.png")
	defer f1.Close()
	img1, _, _ := image.Decode(f1)

	maxX, maxY := img1.Bounds().Max.X, img1.Bounds().Max.Y

	colorArr := [][3]uint32{}

	for i := 0; i < maxX; i = i + (int(step * 10000)) {
		for j := 0; j < maxY; j = j + (int(step * 10000)) {
			r, g, b, _ := img1.At(i, j).RGBA()

			isCunzai := false
			for _, v := range colorArr {
				if r == v[0] && g == v[1] && b == v[2] {
					isCunzai = true
					break
				}
			}
			if !isCunzai {
				colorArr = append(colorArr, [3]uint32{r, g, b})
			}
			if r == 0 && g == 0 && b == 0 {
				continue
			} else {
				lng := float64(i)*0.0001 + minLng
				lat := maxLat - float64(j)*0.0001
				//保持先lat后lng
				landM[[2]int{
					int(math.Round(lat * precision)),
					int(math.Round(lng * precision)),
				}] = struct{}{}
			}
		}
	}
	return landM
}

var grayNum = 0
var landNum = 0
var effectNum = 0

var allT1 = 0
var allT2 = 0
var allT3 = 0

// 根据方向获取一个点的所有可以的邻居
func getNeighbor(minItem [3]float64, motions [][2]float64, grayMap map[[2]int]int, step float64, isOut bool) [][2]float64 {
	// 判断点是否在rectangleList中的矩形内

	//var list [][2]float64
	list := make([][2]float64, 0, 8)

	t11 := time.Now().UnixNano()
	for _, offset := range motions {

		//我也不太知道为啥放大之后效果更好!!! 现在知道了，只有在估计距离小于实际距离时候才可以达到整体最优
		lat := minItem[1] + offset[1]*0.0001*1
		lon := minItem[2] + offset[0]*0.0001*1

		//只在中间那段用地图大格子
		//_, isLand := landMap[[2]int{
		//	int(lat * 10000),
		//	int(lon * 10000),
		//}]

		_, isLand := landMapBig[[2]int{
			int(lat*1000 + 1),
			int(lon * 1000),
		}]

		if !isLand {
			//为什么+1呢，核心就是 36.1234，120.1234这种小格子是在36.124这个数大一点的格子里面的，所以要+1；经度是在120.123这个数小一点的格子里面的

			_, isGray := grayMap[[2]int{
				int(lat * 10000),
				int(lon * 10000),
			}]

			if !isGray {

				list = append(list, [2]float64{lat, lon})

				grayMap[[2]int{
					int(lat*1000 + 1),
					int(lon * 1000),
				}] = 0

			} else {
				list = append(list, [2]float64{999.0, 999.0})
			}

		} else {
			list = append(list, [2]float64{999.0, 999.0})
		}

	}
	t12 := time.Now().UnixNano()
	allT1 += int(t12 - t11)

	return list
}

// 对minItem进行正方形涂灰
func paintGray(minItem [3]float64, grayMap map[[2]int]int, step, cellSize float64) {
	//cellSize = 0.0001
	//offset := step * 0.65
	//for i := minItem[1] - offset; i < minItem[1]+offset; i += cellSize {
	//	for j := minItem[2] - offset; j < minItem[2]+offset; j += cellSize {
	//		//grayMap[utils.Float64ToFixedStr(i, 4)+","+utils.Float64ToFixedStr(j, 4)] = struct{}{}
	//
	//		grayMap[[2]int{
	//			int(i * 10000),
	//			int(j * 10000),
	//		}] = struct{}{}
	//	}
	//}

	//大格点版本
	//offset := step * 0.7
	//for i := minItem[1] - offset + 0.002; i <= minItem[1]+offset; i += cellSize {
	//	for j := minItem[2] - offset + 0.001; j <= minItem[2]+offset-0.001; j += cellSize {
	//		grayMap[[2]int{
	//			int(i * 1000),
	//			int(j * 1000),
	//		}] = struct{}{}
	//	}
	//}

	//大格点版本+整数   和上面那个速度没区别
	offset := 35
	latInt := int(math.Round(minItem[1] * 10000))
	lonInt := int(math.Round(minItem[2] * 10000))

	//for i := latInt - offset + 20; i <= latInt+offset; i += 10 {
	//	for j := lonInt - offset + 10; j <= lonInt+offset-10; j += 10 {
	//		grayMap[[2]int{
	//			i / 10,
	//			j / 10,
	//		}] = struct{}{}
	//	}
	//}

	for i := latInt - offset + 20; i <= latInt+offset; i += 10 {
		for j := lonInt - offset + 10; j <= lonInt+offset-10; j += 10 {
			//grayMap[[2]int{
			//	i / 10,
			//	j / 10,
			//}] = struct{}{}
			_, isGray := grayMap[[2]int{
				i / 10,
				j / 10,
			}]
			if !isGray {
				grayMap[[2]int{
					i / 10,
					j / 10,
				}] = 0
			}

		}
	}

	//grayMap[[2]int{
	//	latInt / 10,
	//	lonInt / 10,
	//}] = struct{}{}
}

func getDistance(lat1, lng1, lat2, lng2 float64) float64 {
	//return math.Sqrt(math.Pow(lat1-lat2, 2) + math.Pow(lng1-lng2, 2))
	//	欧式距离
	return math.Abs(lat1-lat2) + math.Abs(lng1-lng2)
}

func getDistanceWeight(lat1, lng1, lat2, lng2 float64, minItem [3]float64) float64 {
	//return math.Sqrt(math.Pow(lat1-lat2, 2) + math.Pow(lng1-lng2, 2))
	//	计算lat1, lng1, lat2, lng2连线的角度
	angle := math.Atan2(lat2-lat1, lng2-lng1)
	//	计算lat2, lng2, minItem[1], minItem[2]连线的角度
	angle2 := math.Atan2(minItem[1]-lat2, minItem[2]-lng2)
	//	计算两个角度的差值
	angle3 := math.Abs(angle - angle2)
	//fmt.Print(angle3)
	if angle3 < math.Pi {
		return math.Sqrt(math.Pow(lat1-lat2, 2)+math.Pow(lng1-lng2, 2)) * 1
	} else {
		return math.Sqrt(math.Pow(lat1-lat2, 2)+math.Pow(lng1-lng2, 2)) * 1

	}
}

// 判断两点之间是否有障碍物
func isInLand(p1, p2 [2]int, landMap map[[2]int]struct{}) bool {
	// 获取直线路径上的所有点
	points := getPointsOnLine(p1, p2)

	// 检查每个点是否存在于陆地地图中
	for _, point := range points {
		if _, ok := landMap[point]; ok {
			return true
		}
	}

	return false
}

// 获取两点之间的直线路径上的所有点
// 获取两点之间的直线路径上的每隔5个单位取一个点
func getPointsOnLine(p1, p2 [2]int) [][2]int {
	points := make([][2]int, 15)

	// 提取两点的坐标
	x1, y1 := p1[0], p1[1]
	x2, y2 := p2[0], p2[1]

	//计算直线路径的总距离
	dx := abs(x2 - x1)
	dy := abs(y2 - y1)
	distance := max(dx, dy)

	// 计算每个单位距离的增量
	xIncrement := float64(x2-x1) / float64(distance)
	yIncrement := float64(y2-y1) / float64(distance)

	// 添加起始点
	points = append(points, [2]int{x1, y1})

	//每隔5个单位取一个点，并添加到结果列表中
	for i := 1; i <= distance; i += 10 {
		x := int(float64(x1) + float64(i)*xIncrement)
		y := int(float64(y1) + float64(i)*yIncrement)
		points = append(points, [2]int{x, y})
		//大格点版本
		//points = append(points, [2]int{x / 10, y / 10})
	}

	//x1, y1 := p1[0], p1[1]
	//x2, y2 := p2[0], p2[1]
	//dx := x2 - x1
	//dy := y2 - y1
	//for i := 1; i < 10; i++ {
	//	points = append(points, [2]int{(x1 + dx*i/10) / 10, (y1 + dy*i/10) / 10})
	//}

	return points
}

// 返回两个整数中的最大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 计算整数的绝对值
func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

// 根据relationMap获取路径
func getPath(relationMap map[[2]int][3]int, start, endMin, end [2]int) []string {
	var path [][2]int
	var result []string
	path = append(path, endMin)
	result = append(result, utils.Float64ToFixedStr(float64(end[0])/10000, 4)+","+utils.Float64ToFixedStr(float64(end[1])/10000, 4), "-1")
	result = append(result, utils.Float64ToFixedStr(float64(endMin[0])/10000, 4)+","+utils.Float64ToFixedStr(float64(endMin[1])/10000, 4), "-1")

	angle := -1

	//维护一个抖动队列
	//var queue = []int{-1, -1, -1}

	for {

		//angle = relationMap[path[len(path)-1]][2]
		path = append(path, [2]int{
			relationMap[path[len(path)-1]][0],
			relationMap[path[len(path)-1]][1],
		})

		if relationMap[path[len(path)-1]][2] != angle {
			//if len(queue) < 3 {
			//	queue = append(queue, angle)
			//	angle = relationMap[path[len(path)-1]][2]
			//	result = append(result, utils.Float64ToFixedStr(float64(path[len(path)-1][0])/10000, 4)+","+utils.Float64ToFixedStr(float64(path[len(path)-1][1])/10000, 4))
			//} else {
			//	if queue[1] == angle {
			//		angle = relationMap[path[len(path)-1]][2]
			//		//angle = relationMap[path[len(path)-1]][2]
			//		//result = append(result, utils.Float64ToFixedStr(float64(path[len(path)-1][0])/10000, 4)+","+utils.Float64ToFixedStr(float64(path[len(path)-1][1])/10000, 4))
			//	} else {
			//		//替换位置
			//		queue[0] = queue[1]
			//		queue[1] = queue[2]
			//		queue[2] = angle
			//		angle = relationMap[path[len(path)-1]][2]
			//		result = append(result, utils.Float64ToFixedStr(float64(path[len(path)-1][0])/10000, 4)+","+utils.Float64ToFixedStr(float64(path[len(path)-1][1])/10000, 4))
			//	}
			//}

			angle = relationMap[path[len(path)-1]][2]
			result = append(result, utils.Float64ToFixedStr(float64(path[len(path)-1][0])/10000, 4)+","+utils.Float64ToFixedStr(float64(path[len(path)-1][1])/10000, 4), strconv.Itoa(angle))

		}
		if path[len(path)-1] == start {
			angle = relationMap[path[len(path)-1]][2]
			result = append(result, utils.Float64ToFixedStr(float64(start[0])/10000, 4)+","+utils.Float64ToFixedStr(float64(start[1])/10000, 4), strconv.Itoa(angle))
			break
		}

	}

	var finalResult []string
	finalResult = append(finalResult, result[0])
	//var queue = []string{result[1], result[3], result[5]}

	for i, _ := range result {

		if i%2 == 0 {
			//if queue[1] != result[i+1] {
			//	queue[0] = queue[1]
			//	queue[1] = queue[2]
			//	queue[2] = result[i+1]
			//	finalResult = append(finalResult, result[i])
			//}
			finalResult = append(finalResult, result[i])
		}
	}

	//fmt.Println(len(finalResult), len(result)/2)
	return finalResult
}

// getPointBuffer 算出起始点和目标点的缓冲区外点。如果本身就在缓冲区外就不用算了
func getPointBuffer(req *HtAStarReq) ([]float64, []float64) {
	var motions [][2]float64
	angle := 32
	//每次扩展的长度
	step := 0.005
	for i := 0; i < angle; i++ {
		motions = append(motions, [2]float64{math.Cos(float64(i) * 2 * math.Pi / float64(angle)), math.Sin(float64(i) * 2 * math.Pi / float64(angle))})
	}

	var startBuffer []float64
	var endBuffer []float64
	wgBuffer := sync.WaitGroup{}
	wgBuffer.Add(2)
	for i, v := range [2][]float64{req.Start, req.End} {
		go func(v []float64, i int) {
			if i == 0 {
				//startBuffer = func1Five(motions, step, [][]float64{v}, req.End)
				var ch1 = make(chan []float64, 10)
				ch1 <- v
				close(ch1)
				//grayStart := make(map[[2]int]int, 2000)
				grayStart := sync.Map{}

				startBuffer = func1(motions, step, ch1, req.End, &grayStart)

				//_, isLand := landMapBig[[2]int{
				//	int(v[0]*1000 + 1),
				//	int(v[1] * 1000),
				//}]
				//if !isLand {
				//	startBuffer = func8(motions, step, v, req.End)
				//} else {
				//	startBuffer = v
				//}

			} else {
				//endBuffer = func1Five(motions, step, [][]float64{v}, req.Start)
				var ch1 = make(chan []float64, 10)
				ch1 <- v
				close(ch1)
				grayEnd := sync.Map{}
				endBuffer = func1(motions, step, ch1, req.Start, &grayEnd)

				//endBuffer = func8(motions, step, v, req.Start)

				//_, isLand := landMapBig[[2]int{
				//	int(v[0]*1000 + 1),
				//	int(v[1] * 1000),
				//}]
				//if !isLand {
				//	endBuffer = func8(motions, step, v, req.Start)
				//} else {
				//	endBuffer = v
				//}
			}
			wgBuffer.Done()
		}(v, i)
	}
	wgBuffer.Wait()
	return startBuffer, endBuffer
}

func func8(motions [][2]float64, step float64, point []float64, oPoint []float64) []float64 {

	var bufferPoints [][]float64
	for angleIdx, offset := range motions {
		lat := point[0] + offset[1]*step
		lon := point[1] + offset[0]*step
		if !forward(motions, []float64{lat, lon}, angleIdx, 0.005) {
			//return func8(motions, step+0.005, []float64{lat, lon}, oPoint)
			//return []float64{lat, lon}
			bufferPoints = append(bufferPoints, []float64{lat, lon})
		}
	}
	if len(bufferPoints) != 0 {
		minDis := bufferPoints[0]
		for _, v := range bufferPoints {
			if getDistance(v[0], v[1], oPoint[0], oPoint[1]) < getDistance(minDis[0], minDis[1], oPoint[0], oPoint[1]) {
				minDis = v
			}
		}
		return minDis
	}
	return func8(motions, step+0.001, point, oPoint)
}

func forward(motions [][2]float64, point []float64, angleIdx int, step float64) bool {
	for _, offset := range motions {
		lat := point[0] + offset[1]*step
		lon := point[1] + offset[0]*step

		_, isLand := landMapBig[[2]int{
			int(lat*1000 + 1),
			int(lon * 1000),
		}]
		if isLand {
			return true
		}
	}
	return false
}

func func1(motions [][2]float64, step float64, points chan []float64, oPoint []float64, gray *sync.Map) []float64 {

	var tempPoints = make(chan []float64, len(points)*32)
	var okPoints = make(chan []float64, len(points))
	var ch1 = make(chan []float64, len(points))
	var wgFunc1 sync.WaitGroup

	wgFunc1.Add(1)
	go func() {
		for point := range points {
			ch1 <- point
		}
		wgFunc1.Done()
		close(ch1)
	}()

	for i := 0; i < 2; i++ {
		wgFunc1.Add(1)
		go func() {
			defer wgFunc1.Done()
			for point := range ch1 {
				landNum1 := 0
				for _, offset := range motions {
					lat := point[0] + offset[1]*step
					lon := point[1] + offset[0]*step
					//_, isLand := landMap[[2]int{
					//	int(lat * 10000),
					//	int(lon * 10000),
					//}]
					_, isLand := landMapBig[[2]int{
						int(lat*1000 + 1),
						int(lon * 1000),
					}]
					if !isLand {
						//tempPoints <- []float64{lat, lon}

						//grayNum1, isGray := gray[[2]int{
						//	int(lat*1000 + 1),
						//	int(lon * 1000),
						//}]

						grayNum1, isGray := gray.Load([2]int{
							int(lat*1000 + 1),
							int(lon * 1000),
						})
						if !isGray {
							tempPoints <- []float64{lat, lon}
							//gray[[2]int{
							//	int(lat*1000 + 1),
							//	int(lon * 1000),
							//}] = 0
							gray.Store([2]int{
								int(lat*1000 + 1),
								int(lon * 1000),
							}, 0)
						} else {
							//第二个用到浓度的地方，20这个数随便整的
							if grayNum1.(int) < 20 {
								tempPoints <- []float64{lat, lon}
								gray.Store([2]int{
									int(lat*1000 + 1),
									int(lon * 1000),
								}, grayNum1.(int)+1)
							}
						}

					} else {
						landNum1++
					}
				}
				//如果其中一个点可以，暂时保存
				if landNum1 == 0 {
					okPoints <- []float64{point[0], point[1], getDistance(point[0], point[1], oPoint[0], oPoint[1])}
				}
			}
		}()
	}

	//打印wgFunc1的数量
	wgFunc1.Wait()

	if len(okPoints) != 0 {
		close(okPoints)
		minDis := <-okPoints
		for v := range okPoints {
			if v[2] < minDis[2] {
				minDis = v
			}
		}
		return []float64{minDis[0], minDis[1]}
	} else {
		close(tempPoints)
		return func1(motions, step, tempPoints, oPoint, gray)
	}
}

func readLandTxt(name string) map[[2]int]struct{} {
	m := make(map[[2]int]struct{}, 250000)
	f1, _ := os.Open(name)
	scanner := bufio.NewScanner(f1)
	for scanner.Scan() {
		line := scanner.Text()
		lat, _ := strconv.ParseFloat(strings.Split(line, ",")[0], 64)
		lon, _ := strconv.ParseFloat(strings.Split(line, ",")[1], 64)
		m[[2]int{
			int(lat),
			int(lon),
		}] = struct{}{}
	}
	f1.Close()

	return m
}
